﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PrimeNumber
{
    class Prime
    {
        static void Main(string[] args)
        {
            Console.Write("请输入寻找的数：");

            int num = Convert.ToInt32(Console.ReadLine());

            bool prime = true;
            bool selfPrime = true;

            Console.Write("素数因子为(无重复）：");

            if (num <= 1)
            {
                Console.WriteLine("该数没有素数因子");
            }
            else
            {
                for (int i = 2; i <= num / 2; i++) // 折中算法节省时间
                {
                    if (num % i == 0) // 因数
                    {
                        selfPrime = false;
                        //list.Add(i);
                        for (int j = 2; j <= Math.Sqrt(i); j++) //判断是否为素因数
                        {
                            if (i % j == 0)
                            {
                                prime = false;
                                break;
                            }
                        }

                        if (prime)
                        {
                            Console.Write(i + " ");
                        }
                        prime = true;
                    }
                }
                if(selfPrime)//自身为素数
                {
                    Console.Write(num);

                }
                else // 自身不为素数时的组合（有重复素因数）
                {
                    Console.WriteLine();
                    Console.Write("素数因子表达式为"+num+" = ");
                    int numcopy = num;
                    while (numcopy != 1)
                    {
                        bool half = true;
                        for (int i = 2; i <= numcopy / 2; i++)  // 如果在一半的搜寻之后都没有，它此时一定是素数
                        {
                            if (numcopy % i == 0) // 整除
                            {
                                half = false;
                                Console.Write(i + "*");
                                numcopy = numcopy / i;
                                break;
                            }
                        }
                        if (half)
                        {
                            Console.Write(numcopy);
                            numcopy = 1;
                        }
                    }
                }

            }

        }
    }
}
